package Demo5;

import java.util.Arrays;
//有效三角形的个数
public class Solution {
    public int triangleNumber(int[] nums) {
    //1、优化：排序
    Arrays.sort(nums);

    //2、利用双指针解决问题
    int ret = 0;
    for(int i = nums.length-1;i >= 2;i--){
        //利用双指针快速统计出符合条件的三角形的个数
        int left = 0;
        int right = i-1;

        while(left < right){
            if(nums[left]+nums[right] > nums[i]){
                ret += (right - left);
                right--;
            }else{
                left++;
            }
        }
    }
    return ret;
}
}
